package sort.memory;

import java.util.Arrays;

//1,3,8-0,2,4
//0-1,3,8-2,4
//0,1-3,8-2,4
//0,1,2-3,8-4
//0,1,2,3-8-4
//0,1,2,3,4-8

public class MergeSortLinked {
    public static void main(String[] args) {

        int[] array = SortUtil.newArray(11);
        System.out.println(Arrays.toString(array));

        ListNode head = SortUtil.toLinked(array);
        MergeSortLinked solution = new MergeSortLinked();
        ListNode newHead = solution.sortList(head);

        SortUtil.print(newHead);
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        //找到中间节点，并切断连接
        ListNode middle = findMiddle(head);
        ListNode middleNext = middle.next;
        middle.next = null;

        ListNode head1 = sortList(head);
        ListNode head2 = sortList(middleNext);
        return merge(head1, head2);
    }

    /**
     * 快慢指针方法找到中间节点
     * @param start
     * @return
     */
    public ListNode findMiddle(ListNode start) {
        ListNode slow = start;
        ListNode fast = start.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode headPre = new ListNode();
        ListNode newEnd = headPre;

        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                newEnd = newEnd.next = head1;
                head1 = head1.next;
            } else {
                newEnd = newEnd.next = head2;
                head2 = head2.next;
            }
        }

        //处理剩余的
        if (head1 != null) {
            newEnd.next = head1;
        } else if (head2 != null) {
            newEnd.next = head2;
        }

        return headPre.next;
    }
}